|
The dead-end elimination algorithm (DEE) is a method for minimizing a function over a discrete set of independent variables. The basic idea is to identify "dead ends", i.e., combinations of variables that are not necessary to define a global minimum because there is always a way of replacing such combination by a better or equivalent one. Then we can refrain from searching such combinations further. Hence, dead-end elimination is a mirror image of dynamic programming, in which "good" combinations are identified and explored further. Although the method itself is general, it has been developed and applied mainly to the problems of predicting and designing the structures of proteins. It closely related to the notion of dominance in optimization also known as substitutability in a Constraint Satisfaction Problem. The original description and proof of the dead-end elimination theorem can be found in . ==Basic requirements== An effective DEE implementation requires four pieces of information: # A well-defined finite set of discrete independent variables # A precomputed numerical value (considered the "energy") associated with each element in the set of variables (and possibly with their pairs, triples, etc.) # A criterion or criteria for determining when an element is a "dead end", that is, when it cannot possibly be a member of the solution set # An objective function (considered the "energy function") to be minimized Note that the criteria can easily be reversed to identify the maximum of a given function as well. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dead-end elimination」の詳細全文を読む スポンサード リンク
|